“I could be bounded in a nutshell and count myself a king of infinite space” - Shakespeare, Hamlet
For simplicity, the only official quantifiers in Predicate Logic and the “bare” universal and existential quantifiers. But we rarely see these in practice; most applications involve quantifying not over everything in the universe, but over some restricted set or domain. Here we show that Predicate Logic still suffices for real mathematics, because restricted quantifiers can be viewed as (extremely useful) abbreviations for more complex formulas. ## Important Abbreviations
Definition
“For every \(x\) such that …, \(P(x)\) holds: > >\[ >\begin{array}{lcl} > \forall x{\in}S\ \, P(x) & := & \forall x\ (\,x\in S\ \to\ P(x)\,) \\ > \forall x{\leq}N\ \, P(x)& := &\forall x\ (\,x\leq N\ \to\ P(x)\,) \\[10pt] > \mathrm{etc.}\\ > \end{array} >\]
(where the \(~:=~\) operator means we are defining the left-hand-side to be equal to the right-hand-side).
Definition
“For some \(x\) such that …, \(P(x)\) holds: >\[ >\begin{array}{lcl} > \exists x{\in}S\ \, P(x)& := &\exists x\ (\,x\in S\ \land\ P(x)\,) \\ > \exists x{\leq}N\ \, P(x)& := &\exists x\ (\,x\leq N\ \land\ P(x)\,) \\[10pt] > \mathrm{etc.}\\ > \end{array} >\]
Definition
“There exists a unique \(x\) such that … where \(P(x)\) holds: > >\[ >\begin{array}{lcl} > \exists!x{\in}S\ \, P(x)& := &\exists x\ \bigl(x\in S \land P(x) \land \forall y\ (y \in S \land P(y) \ \to\ x = y)\bigr) \\ > \qquad\mathrm{or} & := &\exists x\ \bigl(x\in S \land P(x) \land \lnot\exists y\ (y \in S \land P(y) \land x \not= y)\bigr) \\ > \end{array} >\]
Example
The following equivalences hold and should be memorized. > Basically, they say that rules for pushing a negation into a quantified formula are the same for restricted quantifiers as we saw earlier for bare quantifiers. > >\[ >\begin{array}{lcl} > \lnot \forall x{\in}S\ \ P(x) & \equiv & \exists x{\in}S\ \ \ \lnot P(x) \\ > \lnot \forall x{\leq}N\ \ P(x) & \equiv & \exists x{\leq}N\ \ \ \lnot P(x) \\[10pt] > \lnot \exists x{\in}S\ \ P(x) & \equiv & \forall x{\in}S\ \ \ \lnot P(x) \\ > \lnot \exists x{\leq}N\ \ P(x) & \equiv & \forall x{\leq}N\ \ \ \lnot P(x) \\ > \end{array} >\] These equivalences can all be verified by expanding the formulas into their more primitive forms, and then applying familiar rules of logical equivalence.
We can verify the first equivalence above as follows: \[ \begin{array}{lcl} \lnot \forall x{\in}S\ \ P(x) & = & \lnot \forall x\ (x\in S\ \to\ P(x)) \\ &\equiv & \exists x\ \lnot (x\in S\ \to\ P(x)) \\ &\equiv & \exists x\ (x\in S\ \land\ \lnot P(x)) \\ &= & \exists x{\in}S\ \ \ \lnot P(x) \\ \end{array} \] in general, we will work directly with bounded quantifiers and ignore the fact that logicians treat them as abbreviations for more primitive concepts.
Previous: 3.2 Proofs for Humans
Next: 3.4 Proving Implications